package search;

import hexgame.GameState;

import hexgame.GameLogic;
import hexgame.HexMove;
import hexgame.HexPlayer;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.HashMap;

public class Search {
	/**
	 * Returns the turns which the shortest route to the edge still requires to be made.
	 * @param start - The tile to start on. Should have the current player colour or NONE in it to get the shortest valid route
	 * @param state - The GameState to search
	 * @param rightEdge - true if we are searching towards right edge, false if we are searching towards the bottom
	 * @return The path *excluding* any moves which the player has already made. Null if no path
	 */
	public static HexMove[] leastTurnsToEdge(HexMove start, GameState state, boolean rightEdge) {
		
		HexMove[] moves = leastTurnsToEdgePath(start, state, rightEdge);
		
		if(moves == null) {
			return null;
		}
		
		List<HexMove> finalMoves = new ArrayList<HexMove>();
		for(HexMove move : moves) {
			if(state.getHexState(move) == HexPlayer.NONE) {
				finalMoves.add(move);
			}
		}
		
		if(finalMoves.size() == 0) {
			return new HexMove[0];
		}
		
		return finalMoves.toArray(new HexMove[finalMoves.size()]);
	}
	
	/**
	 * Returns the path which the shortest route to the edge takes. This includes moves already made by the colour provided by the HexMove start
	 * @param start - The tile to start on. Should have the current player colour or NONE in it to get the shortest valid route
	 * @param state - The GameState to search
	 * @param rightEdge - true if we are searching towards right edge, false if we are searching towards the bottom
	 * @return The path *including* any moves which the player has already made. Null if no path
	 */
	public static HexMove[] leastTurnsToEdgePath(HexMove start, GameState state, boolean rightEdge) {

		Map<HexMove, Integer> estFinalCost = new HashMap<HexMove, Integer>();
		
		Map<HexMove, Integer> costStartToNode = new HashMap<HexMove, Integer>();
		
		Map<HexMove, HexMove> edgeTowardsStart = new HashMap<HexMove, HexMove>();
		
		ArrayList<HexMove> openSet = new ArrayList<HexMove>();
		openSet.add(start);
		costStartToNode.put(start, 0);
		
		List<HexMove> closedSet = new ArrayList<HexMove>();
		
		while(openSet.size() > 0) {
			// Get node in openSet with lowest estFinalCost value (if it has a value)
			HexMove node = null;
			for(HexMove move : openSet) {
				if(node == null) {
					node = move;
					continue;
				}
				// Get the cost of this move
				Integer cost = estFinalCost.get(move);
				
				if(cost != null) {
					// Get the cost of the current best node
					Integer currentCost = estFinalCost.get(node);
					if(currentCost == null) {
						node = move;
					}
					else if(cost < currentCost) {
						node = move;
					}
				}
			}
			// if node is at goal then get path from edgeTowardsStart Map.
			if(rawDistanceToEdge(node, rightEdge, state) == 0) {
				// reconstruct path
				ArrayList<HexMove> finalMovesReversed = new ArrayList<HexMove>();
				
				HexMove prev = node;
				
				while(edgeTowardsStart.get(prev) != null) {
					finalMovesReversed.add(prev);
					prev = edgeTowardsStart.get(prev);
				}
				finalMovesReversed.add(start);
				
				HexMove[] finalResult = new HexMove[finalMovesReversed.size()];
				
				for(int i=0; i<finalMovesReversed.size(); i++) {
					finalResult[i] = finalMovesReversed.get(finalMovesReversed.size() - i - 1);
				}
				
				return finalResult;
			}
			
			// take node from openSet and put in closedSet
			openSet.remove(node);
			closedSet.add(node);
			
			// Get every neighbour of node which is either the same colour as node or has no colour (NONE)
			Collection<HexMove> neighbours = GameLogic.getConnectingMoves(node, state);
			
			// go through every neighbour (which is either same type or NONE)
			for(HexMove neighbour : neighbours) {
				
				// If the two nodes are the same colour as the player colour, they have a cost of zero
				int costBetween = (neighbour.getPlayer() == start.getPlayer() ? 0 : 1);
				
				int tempScore = costStartToNode.get(node) + costBetween;
				
				if(closedSet.contains(neighbour) && tempScore >= costStartToNode.get(neighbour)) {
					continue;
				}
			
				if(!openSet.contains(neighbour) || (tempScore < costStartToNode.get(neighbour))) {
					edgeTowardsStart.put(neighbour, node);
					costStartToNode.put(neighbour, tempScore);
					estFinalCost.put(neighbour, tempScore + rawDistanceToEdge(neighbour, rightEdge, state));
					if(!openSet.contains(neighbour)) {
						openSet.add(neighbour);
					}
				}
			}			
		}
		return null;
	}
	
	/**
	 * Returns the turns which the shortest route to the edge still requires to be made.
	 * @param start - The tile to start on. Should have the current player colour or NONE in it to get the shortest valid route
	 * @param state - The GameState to search
	 * @param rightEdge - true if we are searching towards right edge, false if we are searching towards the bottom
	 * @return The path *excluding* any moves which the player has already made
	 */
	public static HexMove[] leastTurnsToEdgeBridge(HexMove start, GameState state, boolean rightEdge) {
		
		HexMove[] moves = leastTurnsToEdgePath(start, state, rightEdge);
		
		if(moves == null) {
			return null;
		}
		
		List<HexMove> finalMoves = new ArrayList<HexMove>();
		for(HexMove move : moves) {
			if(state.getHexState(move) == HexPlayer.NONE) {
				finalMoves.add(move);
			}
		}
		
		if(finalMoves.size() == 0) {
			return new HexMove[0];
		}
		
		return finalMoves.toArray(new HexMove[finalMoves.size()]);
	}
	
	/**
	 * Returns the path which the shortest route to the edge takes. This includes moves already made by the colour provided by the HexMove start
	 * @param start - The tile to start on. Should have the current player colour or NONE in it to get the shortest valid route
	 * @param state - The GameState to search
	 * @param rightEdge - true if we are searching towards right edge, false if we are searching towards the bottom
	 * @return The path *including* any moves which the player has already made
	 */
	public static HexMove[] leastTurnsToEdgePathBridge(HexMove start, GameState state, boolean rightEdge) {

		Map<HexMove, Integer> estFinalCost = new HashMap<HexMove, Integer>();
		
		Map<HexMove, Integer> costStartToNode = new HashMap<HexMove, Integer>();
		
		Map<HexMove, HexMove> edgeTowardsStart = new HashMap<HexMove, HexMove>();
		
		ArrayList<HexMove> openSet = new ArrayList<HexMove>();
		openSet.add(start);
		costStartToNode.put(start, 0);
		
		List<HexMove> closedSet = new ArrayList<HexMove>();
		
		while(openSet.size() > 0) {
			// Get node in openSet with lowest estFinalCost value (if it has a value)
			HexMove node = null;
			for(HexMove move : openSet) {
				if(node == null) {
					node = move;
				}
				// Get the cost of this move
				Integer cost = estFinalCost.get(move);
				
				if(cost != null) {
					// Get the cost of the current best node
					Integer currentCost = estFinalCost.get(node);
					if(currentCost == null) {
						node = move;
					}
					else if(cost < currentCost) {
						node = move;
					}
				}
			}
			// if node is at goal then get path from edgeTowardsStart Map.
			if(rawDistanceToEdge(node, rightEdge, state) == 0) {
				// reconstruct path
				ArrayList<HexMove> finalMovesReversed = new ArrayList<HexMove>();
				
				HexMove prev = node;
				
				while(edgeTowardsStart.get(prev) != null) {
					finalMovesReversed.add(prev);
					prev = edgeTowardsStart.get(prev);
				}
				finalMovesReversed.add(start);
				
				HexMove[] finalResult = new HexMove[finalMovesReversed.size()];
				
				for(int i=0; i<finalMovesReversed.size(); i++) {
					finalResult[i] = finalMovesReversed.get(finalMovesReversed.size() - i - 1);
				}
				
				return finalResult;
			}
			
			// take node from openSet and put in closedSet
			openSet.remove(node);
			closedSet.add(node);
			
			// Get every neighbour of node which is either the same colour as node or has no colour (NONE)
			Collection<HexMove> neighbours = GameLogic.getValidZeroConnectedHexagons(node, state);
			
			// go through every neighbour (which is either same type or NONE)
			for(HexMove neighbour : neighbours) {
				
				// If the two nodes are the same colour as the player colour, they have a cost of zero
				int costBetween = (neighbour.getPlayer() == start.getPlayer() ? 0 : 1);
				
				int tempScore = costStartToNode.get(node) + costBetween;
				
				if(closedSet.contains(neighbour) && tempScore >= costStartToNode.get(neighbour)) {
					continue;
				}
			
				if(!openSet.contains(neighbour) || (tempScore < costStartToNode.get(neighbour))) {
					edgeTowardsStart.put(neighbour, node);
					costStartToNode.put(neighbour, tempScore);
					estFinalCost.put(neighbour, tempScore + rawDistanceToEdge(neighbour, rightEdge, state));
					if(!openSet.contains(neighbour)) {
						openSet.add(neighbour);
					}
				}
			}			
		}
		return null;
	}
	
	/**
	 * This method isn't as good as leastTurnsToEdgePath
	 * This exhaustively searches the board for the shortest path from a specified point to an edge
	 * @param start - The start point. This HexMove also specifies the type of tile (RED/BLUE/NONE) to search for
	 * @param state - the GameState to search in
	 * @param rightEdge - Is the target the right edge? (or the bottom edge?)
	 * @return An array containing the shortest path. Returns null on no path found
	 */
	public static HexMove[] shortestPathToEdge(HexMove start, GameState state, boolean rightEdge) {
		int targetRow, targetColumn;
		
		if(rightEdge) {
			targetRow = -1;
			targetColumn = state.getBoardSize() - 1;
		}
		else {
			targetColumn = -1;
			targetRow = state.getBoardSize() - 1;
		}
		ArrayList<HexMove> path = new ArrayList<HexMove>();
		path.add(start);
		
		return shortestPathToEdgeRecursive(start, state, targetRow, targetColumn, new ArrayList<HexMove>(), path);
	}
	
	private static HexMove[] shortestPathToEdgeRecursive(HexMove start, GameState state, int targetRow, int targetColumn, List<HexMove> checkedList, List<HexMove> path) {
		checkedList.add(start);
		
		Collection<HexMove> list = GameLogic.getConnectingHexagons(start, state);
		
		Map<Integer, Set<HexMove>> prioritisedHexagons = new TreeMap<Integer, Set<HexMove>>();
		
		for(HexMove move : list) {
			int rawDistanceToEdge = (state.getBoardSize() - 1);
			if(targetRow == -1) {
				rawDistanceToEdge -= move.getX();
			}
			else {
				rawDistanceToEdge -= move.getY();
			}
			
			if(!prioritisedHexagons.containsKey(rawDistanceToEdge)) {
				prioritisedHexagons.put(rawDistanceToEdge, new HashSet<HexMove>());
			}
			
			prioritisedHexagons.get(rawDistanceToEdge).add(move);
		}
		
		for(Set<HexMove> moves : prioritisedHexagons.values()) {
			for(HexMove move : moves) {
				path.add(move);
				
				if(move.getY() == targetRow || move.getX() == targetColumn) {
					return path.toArray(new HexMove[path.size()]);
				}
				else if(!checkedList.contains(move)) {
					HexMove[] newPath = shortestPathToEdgeRecursive(move, state, targetRow, targetColumn, checkedList, path);
					
					if(newPath != null) {
						return newPath;
					}
				}
				path.remove(move);
			}
		}
		return null;
	}
	
	/**
	 * Returns the distance between node and the target edge.
	 * Does not take into account any obstacles.
	 * @param node - The position to check
	 * @param rightEdge - Should we take the rightEdge as the target or the bottom edge?
	 * @param state - The GameState to get the boardSize from
	 * @return an integer saying how far from the edge we are
	 */
	public static int rawDistanceToEdge(HexMove node, boolean rightEdge, GameState state) {
		int dist = state.getBoardSize() - 1;
		
		if(rightEdge) { 
			return dist - node.getX();
		}
		else {
			return dist - node.getY();
		}
	}
}
